\section{Introduction}
In a dynamic network, nodes (processors/end hosts) and communication
links can appear and disappear at will over time.  Emerging networking
technologies such as ad hoc wireless, sensor, and mobile networks,
overlay and peer-to-peer (P2P) networks are inherently dynamic,
resource-constrained, and unreliable.  This necessitates the
development of a solid theoretical foundation to design efficient,
robust, and scalable distributed algorithms and understand the
fundamental power and limitations of distributed computing on such
networks. Such a foundation is critical to realize the full potential
of these large-scale dynamic networks.

As a step towards this understanding, we investigate dynamic networks
in which the network topology changes arbitrarily from round to round.
We first consider a worst-case model studied by Kuhn, Lynch, and
Oshman~\cite{kuhn+lo:dynamic} in which the communication links for
each round are chosen by an online adversary, and nodes do not know
their neighbors for the current round before they broadcast their
messages. (Note that in this model, only edges change and nodes are
assumed to be fixed.)  The only constraint on the adversary is that
the network should be connected in each round. Unlike prior models on
dynamic networks, this model does not assume that the network
eventually stops changing and requires that the algorithms work
correctly and terminate even in networks that change continually over
time.

In this paper, we study the fundamental problem of information
spreading (also called gossip). In $k$-gossip, there are $k$ pieces of
information (tokens) that are initially present in some nodes and the
problem is to disseminate the $k$ tokens to all the $n$ nodes in the
network. (By just gossip, we mean $n$-gossip.)  Information spreading
is a fundamental primitive for distributed computing useful for
solving problems such as broadcasting and leader election. Indeed,
solving $n$-gossip, where each node starts with exactly one token,
allows any function of the initial states of the nodes to be computed,
assuming the nodes know $n$~\cite{kuhn+lo:dynamic}.

\subsection{Our results}
The focus of this paper is on the power of {\em token-forwarding}\/
algorithms, which do not manipulate tokens in any way other than
storing and forwarding them. Token-forwarding algorithms are simple,
often easy to implement, and typically incur low overhead. In a key
result,~\cite{kuhn+lo:dynamic} showed that in their adversarial model,
$k$-gossip can be solved by token-forwarding in $O(nk)$ rounds, and
any deterministic online token-forwarding algorithm needs $\Omega(n
\log k)$ rounds. They also proved an $\Omega(nk)$ lower bound for a
restricted class of token-forwarding algorithms, called
knowledge-based algorithms.  Our main result is a new lower bound that
applies to {\em any}\/ deterministic online token-forwarding algorithm
for $k$-gossip.
\begin{itemize}
\item
We show that every token-forwarding algorithm for the $k$-gossip problem takes
$\Omega(n + nk/\log n)$ rounds against an adversary that, at the start of
each round, knows the randomness used by the algorithm in the round.
This also implies that any deterministic online token-forwarding
algorithm takes $\Omega(n + nk/\log n)$ rounds.  Our result applies even
to centralized token-forwarding algorithms that have a global
knowledge of the token distribution. 
\end{itemize}
This result resolves an open problem raised in~\cite{kuhn+lo:dynamic},
significantly improving their lower bound for $k = \omega(\log n \log
\log n)$, and matching their upper bound to within a logarithmic
factor.  Our lower bound also enables a better comparison of
token-forwarding with an alternative approach based on network coding
due to ~\cite{haeupler:gossip,haeupler+k:dynamic}, which achieves $O(n
+ nk/\log n)$ rounds using $O(\log n)$-bit messages, and $O(n + k)$
rounds with large message sizes (e.g., $\Theta(n \log n)$ bits).
Thus, for large token and message sizes, our result {\em establishes a
  factor $\Omega(\min\{n,k\}/\log n)$ gap between token-forwarding and
  network coding}, a significant new bound on the network coding
advantage for information dissemination. We note that in our model we
allow only one token per edge per round and thus our bounds hold
regardless of the token size.

Our lower bound indicates that one cannot obtain efficient (i.e.,
subquadratic) token-forwarding algorithms for gossip in the
adversarial model of~\cite{kuhn+lo:dynamic}.  Furthermore, for
arbitrary token sizes, we do not know of any algorithm that is
significantly faster than quadratic time.  This motivates considering
other weaker (and perhaps, more realistic) models of dynamic networks.
In fact, it is not clear whether one can solve the problem
significantly faster even in an offline setting, in which the network
can change arbitrarily each round, but the entire evolution is known
to the algorithm in advance.  Our next contribution takes a step in
resolving this basic question for token-forwarding algorithms.
\begin{itemize}
\item
We present a polynomial-time centralized token-forwarding algorithm
that solves the $k$-gossip problem in the offline setting of an
$n$-node dynamic network in $O(\min\{nk, n \sqrt{k \log n}\})$ rounds
with high probability.
\item
We also present a polynomial-time centralized token-forwarding
algorithm that solves the $k$-gossip problem in the offline setting in
$O(n^\eps)$ times the optimal number of rounds, for any $\eps > 0$,
assuming the algorithm is allowed to transmit $O(\log n)$ tokens per
round.
\end{itemize}
Our upper bounds show that in the offline setting,
token-forwarding algorithms can achieve a time bound that is within
$O(\sqrt{k\log n})$ of the information-theoretic lower bound of
$\Omega(n + k)$, and that we can approximate the best token-forwarding
algorithm to within a $O(n^\eps)$ factor, with logarithmic extra
bandwidth per edge.

\subsection{Related work}
Information spreading (or dissemination) in networks is one of the
most basic problems in computing and has a rich literature. \junk{Here
  we focus mostly on work that is relevant to our work.} The problem
is generally well-understood on static networks, both for
interconnection networks~\cite{leighton:book} as well as general
networks~\cite{lynch:distributed,attiya+w:distributed}.  In
particular, the $k$-gossip problem can be solved in $O(n + k)$ rounds
on any $n$-node static network~\cite{topkis:disseminate}.  There also
have been several papers on broadcasting, multicasting, and related
problems in static heterogeneous and wireless networks (e.g.,
see~\cite{alon+blp:radio,bar-yehuda+gi:radio,bar-noy+gns:multicast,clementi+ms:radio}).

Dynamic networks have been studied extensively over the past three
decades.  Early studies focused on dynamics that arise when edges or
nodes fail.  A number of fault models, varying according to extent and
nature (e.g., probabilistic vs.\ worst-case) of faults allowed, and
the resulting dynamic networks have been analyzed (e.g.,
see~\cite{attiya+w:distributed,lynch:distributed}).  There have been
several studies that constrain the rate at which changes occur, or
assume that the network eventually stabilizes (e.g.,
see~\cite{afek+ag:dynamic,dolev:stabilize,gafni+b:link-reversal}).

There also has been considerable work on general dynamic networks.
Early studies in this area
include~\cite{afek+gr:slide,awerbuch+pps:dynamic}, which introduce
building blocks for communication protocols on dynamic networks.
\junk{Subsequently, a number of different problems have been studied
  on dynamic and asynchronous networks, including routing, load
  balancing, multicast, anycast, and several fundamental distributed
  computing problems.}  Another notable work is the local balancing
approach of~\cite{awerbuch+l:flow} for solving routing and
multicommodity flow problems on dynamic networks, which has also been
applied to multicast, anycast, and broadcast problems on mobile ad hoc
networks~\cite{awerbuch+bbs:route,awerbuch+bs:anycast,jia+rs:adhoc}.
To address highly unpredictable network dynamics, stronger adversarial
models have been introduced by~\cite{odell+w:dynamic} and others; see
the recent survey of \cite{santoro} and the references therein.  We
adopt the model of~\cite{kuhn+lo:dynamic} in which the set of remains
fixed but the communication graph can change completely from round to
round, with the only constraint being that it stays connected in each
round. \junk{The model of~\cite{kuhn+lo:dynamic} allows for a much
  stronger adversary than the ones considered in past
  work~\cite{awerbuch+l:flow,awerbuch+bbs:route,awerbuch+bs:anycast}.
  There also have been other prior models for dynamic networks similar
  in spirit to the model of ,}

In addition to the $k$-gossip problem,~\cite{kuhn+lo:dynamic}
considers the related problem of counting, and generalizes its results
to the $T$-interval connectivity model, which includes the constraint
that any interval of $T$ rounds has a stable connected spanning
subgraph.  The survey of~\cite{kuhn-survey} summarizes recent work on
dynamic networks.

\junk{ .  Local balancing algorithms, which continually balance the
  packet queues across each edge of the network and drain packets at
  their destination,

It has been shown that assuming the queues at the nodes can hold
enough packets, the local balancing approach can achieve throughput
that is arbitrarily close to the optimal achievable by any offline
algorithm.

Modeling general dynamic networks has gained renewed attention with
the recent advent of heterogeneous networks composed out of ad hoc,
and mobile devices.  }
 
While the model of~\cite{kuhn+lo:dynamic}, as well as ours, allow only
edge changes from round to round, the recent work of \cite{p2p-soda}
introduces a dynamic network model motivated by P2P networks where
both nodes and edges can change by a large amount. They show that
stable almost-everywhere agreement can be efficiently solved in such
networks even in adversarial dynamic settings.  \junk{As in the Kuhn
  et al. model, the algorithms in \cite{p2p-soda} will work and
  terminate correctly even when the network keeps continually
  changing.  We note that there has been considerable prior work in
  dynamic P2P networks (see \cite{p2p-soda, p2p-focs} and the
  references therein) but these don't assume that the network keeps
  continually changing over time.}

Recent work of~\cite{haeupler:gossip,haeupler+k:dynamic} presents
information spreading algorithms based on network
coding~\cite{ahlswede+cly:coding}.  As mentioned earlier, one of their
important results is that the $k$-gossip problem on the adversarial
model of~\cite{kuhn+lo:dynamic} can be solved using network coding in
$O(n+k)$ rounds assuming the token sizes are sufficiently large
($\Omega(n\log n)$ bits). For further references to using network
coding for gossip and related problems, we refer to
~\cite{haeupler:gossip,haeupler+k:dynamic,avin1,avin2,deb+mc:coding,shah}
and the references therein.

Our offline approximation algorithm makes use of results on the
Steiner tree packing problem for directed
graphs~\cite{cheriyan+s:steiner}.  This problem is closely related to
the directed Steiner tree problem (a major open problem in
approximation
algorithms)~\cite{charikar+ccdgg:steiner,zosin+k:steiner} and the gap
between network coding and flow-based solutions for multicast in
arbitrary directed networks~\cite{agarwal+c:coding,sanders+et:flow}.

Finally, we note that a number of recent studies solve $k$-gossip and
related problems using {\em gossip-based}\/ processes, in which each
node exchanges information with a small number of randomly chosen
neighbors in each round.  These processes are attractive owing to
their simplicity of implementation, scalability, and their use in
aggregate computations,
e.g.,~\cite{berenbrink+ceg:gossip,demers,kempe1,chen-spaa,karp,shah,boyd}
and the references therein.  All these studies assume a static
communication network, and do not apply directly to the models
considered in this paper.  A related recent work
is~\cite{avin+kl:dynamic} which analyzes the cover time of random
walks on dynamic networks.




